/**
 * 
 */
package org.wolf.cluster.util;

import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;

/**
 * @author 何小锋
 * 
 */
public class ConsistantHash<T> {
	private static final int DEFAULT_COPYS = 160;
	private HashAlgorithm hashAlg;
	private int numberOfReplicas = DEFAULT_COPYS;
	private SortedMap<Integer, T> circle = new TreeMap<Integer, T>();

	public ConsistantHash(List<T> nodes) {
		this(nodes, new FNVHash1(), DEFAULT_COPYS);
	}

	public ConsistantHash(List<T> nodes, HashAlgorithm hashAlg) {
		this(nodes, hashAlg, DEFAULT_COPYS);
	}

	public ConsistantHash(List<T> nodes, HashAlgorithm hashAlg,
			int numberOfReplicas) {
		this.hashAlg = hashAlg == null ? new FNVHash1() : hashAlg;
		this.numberOfReplicas = numberOfReplicas <= 0 ? DEFAULT_COPYS
				: numberOfReplicas;

		for (T node : nodes) {
			for (int i = 0; i < numberOfReplicas; i++) {
				circle.put(hashAlg.hash(node.toString() + i), node);
			}
		}

	}

	/**
	 * 增加节点
	 * 
	 * @param node
	 */
	public void add(T node) {
		for (int i = 0; i < numberOfReplicas; i++) {
			circle.put(hashAlg.hash(node.toString() + i), node);
		}
	}

	/**
	 * 删除节点
	 * 
	 * @param node
	 */
	public void remove(T node) {
		for (int i = 0; i < numberOfReplicas; i++) {
			circle.remove(hashAlg.hash(node.toString() + i));
		}
	}

	/**
	 * 获取散列值
	 * 
	 * @param key
	 * @return
	 */
	public int hash(String key) {
		return hashAlg.hash(key);
	}

	/**
	 * 根据一个对象的key获得它的将要存储的节点（如：缓存节点）
	 **/
	public T get(String key) {
		if (circle.isEmpty()) {
			return null;
		}
		int hash = hashAlg.hash(key);
		if (!circle.containsKey(hash)) {
			SortedMap<Integer, T> tailMap = circle.tailMap(hash);
			hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
		}
		return circle.get(hash);
	}

	/**
	 * Hash算法
	 * 
	 * @author 何小锋
	 * 
	 */
	public static interface HashAlgorithm {

		public int hash(String key);
	}

	/**
	 * FNVHash1散列
	 * 
	 * @author 何小锋
	 * 
	 */
	public static class FNVHash1 implements HashAlgorithm {
		public int hash(String key) {
			return HashUtil.FNVHash1(key);
		}
	}

}
